// =====================================================================================
//
//       Filename:  antcolony.h
//
//    Description:  Définition générique d'un algorithme d'optimisation par simulation
//					d'une colonie de fourmis
//
//        Version:  1.0
//        Created:  16/09/2009 15:40:00
//       Revision:  none
//       Compiler:  g++
//
//         Author:  François Hissel (fh), francois.hissel@m4x.org
//        Company:
//
// =====================================================================================

#ifndef ANTCOLONY_H_INC
#define ANTCOLONY_H_INC

#include	<list>
#include	"graphe.h"

/**
 * \class AntEdge
 * \brief Arête d'un graphe orienté qui peut être parcouru par des fourmis
 *
 * La classe, héritée de la classe Arc, définit une arête d'un graphe orienté qui peut être parcouru par une colonie de fourmis. En particulier, l'arête contient un membre supplémentaire qui indique la quantité de phéromones qui y ont été déposées.
 */
class AntEdge:public Arc {
	friend class AntGraph;
	public:
		/**
		 * \brief Constructeur standard
		 *
		 * Le constructeur alloue la mémoire nécessaire pour la structure et initialise les champs
		 * \param pid Identifiant
		 * \param *ps1 Sommet d'origine de l'arc
		 * \param *ps2 Sommet extrémité de l'arc
		 * \param ppoids Poids
		 * \param pnom Nom
		 */
		AntEdge(int pid,Sommet *ps1,Sommet *ps2,double ppoids,const string pnom):Arc(pid,ps1,ps2,ppoids,pnom),pheromones(0),add_pheromones(0) {}

		AntEdge(const Arc &a):Arc(a),pheromones(0),add_pheromones(0) {}	//!< Constructeur d'extension à partir d'un arc
	private:
		double pheromones;	//!< Quantité de phéromones présentes sur l'arête
		double add_pheromones;	//!< Quantité de phéromones supplémentaires à déposer sur l'arête
};

/**
 * \class AntGraph
 * \brief Graphe orienté qui peut être parcouru par des fourmis
 *
 * La classe, héritée de la classe Graphe, sert de support à l'algorithme d'optimisation par colonie de fourmis. Tous ses arcs doivent être du type AntEdge, hérité de Arc.
 * L'algorithme de parcours est décrit dans l'article <em>"Ant colonies for the traveling salesman problem - Marco Dorigo, Luca Maria Gambardella - 1996"</em>.
 */
class AntGraph:public Graphe {
	public:
		AntGraph() {}	//!< Constructeur standard, sans initialisation de variables

		/**
		 * \brief Construit un graphe de parcours à partir d'une matrice de distances entre les sommets
		 *
		 * La méthode construit un graphe qui peut être parcour par des fourmis à partir d'une matrice carrée contenant les distances entre chacun des sommets deux à deux. Cela suppose que le graphe est complet, c'est-à-dire que chaque noeud est voisin de tous les autres et est accessible directement par un arc. En revanche, aucune supposition n'est faite sur le caractére symétrique de la matrice. La distance peut varier selon le sens de parcours du trajet.
		 * \param n Nombre de sommets du graphe
		 * \param distances Matrice carrée des distances entre les sommets. Aucune vérification n'est faite sur la taille de la matrice.
		 */
		AntGraph(int n,double **distances);

		/**
		 * \brief Calcul de la tournée la plus courte pour parcourir le graphe
		 *
		 * La méthode simule le passage de nb_ants fourmis sur le réseau à la recherche de la tournée la plus courte. Une tournée correspond ici au parcours de tous les sommets du réseau une et une seule fois, sans retour au point de départ. Chaque fourmi recherche aléatoirement un chemin correct, puis dépose sur le chemin une quantité de phéromones inversement proportionnelle à la longueur de la tournée parcourue.
		 * A chaque fois qu'elle arrive à un nouveau sommet, la fourmi choisit aléatoirement un des arcs accessibles qui en partent avec la probabilité \f[ \frac{\tau_i^{\alpha}\eta_i^{\beta}}{\sum_i{\tau_i^{\alpha}\eta_i^{\beta}}} \f], où \f$ \tau_i \f$ est la quantité de phéromones présente sur l'arc d'indice i, \f$ \eta_i \f$ est l'attractivité de l'arc d'indice i (dans ce cas l'inverse de son poids), et i décrit la liste des voisins accessibles du sommet où se situe la fourmi.
		 * \param iterations Nombre d'itérations à réaliser
		 * \param nb_ants Nombre de fourmis qui parcourent le chemin à chaque itération
		 * \param start Sommet initial de la tournée
		 * \param alpha Paramètre d'attractivité des phéromones (positif ou nul) : plus alpha est grand, plus la fourmi sera attirée par les chemins chargés en phéromones
		 * \param beta Paramètre de visibilité (positif ou nul) : plus beta est grand, moins la fourmi aura tendance à se diriger vers les noeuds les plus éloignés
		 * \param rho Paramètre d'évaporation (compris entre 0 et 1) : plus rho est grand, plus les phéromones s'évaporent rapidement, selon la formule \f$ \tau_i(t+1)=(1-\rho)\tau_i(t) \f$
		 * \return Liste des arêtes de la tournée optimale trouvée
		 */
		list<Arc*> shortest_tour(int iterations,int nb_ants,Sommet *start,double alpha,double beta,double rho);
	private:
		/**
		 * \brief Recherche un chemin de longueur donnée dans le graphe qui ne repasse pas un sommet déjà visité, et en commençant par visiter les arêtes les plus chargées en phéromones
		 *
		 * La fonction est utilisée pour reconstituer un chemin parcourant le graphe en passant par les arêtes les plus chargées en phéromones. Il s'agit d'un algorithme glouton qui visite toujours les sommets voisins en commençant par l'arête la plus odorante et en évitant les sommets déjà visités (repérés grâce à la propriété AntNode::visited). S'il reste bloqué, il retourne à un sommet précédent et choisit la seconde arête la plus odorante, et ainsi de suite jusqu'à trouver un chemin complet.
		 * \param size Taille du chemin à trouver
		 * \param start Noeud initial
		 * \param result Liste des arêtes constituant le chemin optimal
		 * \return Vrai si un chemin a été trouvé, faux sinon
		 */
		bool _travel(int size,Sommet *start,list<Arc*> &result);
};

#endif /* ANTCOLONY_H_INC */
